/*
 * @Author: szx
 * @Date: 2022-03-13 14:08:02
 * @LastEditTime: 2022-03-13 14:11:35
 * @Description:
 * @FilePath: \leetcode\1-99\47\47_2.js
 */
var permuteUnique = function (nums) {
    nums.sort((a, b) => a - b);
    const n = nums.length;
    const res = [];
    const used = new Array(n).fill(false);
    const backtrace = (path) => {
        if (path.length == n) {
            res.push(Array.from(path));
            return;
        }
        for (let i = 0; i < n; i++) {
            if (used[i] || (i > 0 && nums[i] == nums[i - 1] && !used[i - 1])) continue;
            used[i] = true;
            path.push(nums[i]);
            backtrace(path);
            path.pop();
            used[i] = false;
        }
    };
    backtrace([]);
    return res;
};
console.log(permuteUnique([1, 1, 2]));
